#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int mod=998244353;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	priority_queue<int,vector<int>,greater<int> > s;
	int n,m;
	cin >> n >> m;
	int a;
	int sum=0;
	for(int i=1; i<=n; i++)
	{
		cin >> a;
		s.push(a);
	}
	while(s.empty()!=0)
	{
		cout << s.top() << " ";
		s.pop();
	}
	int b,c;
	while(m--)
	{
		cin >> b >> c;
		while(b--)
		{
			int temp=s.top();
			if(temp<c)
			{
				s.pop();
				s.push(c);
			}
			else if(temp>=c)
			{
				break;
			}
			while(s.empty()!=0)
			{
				cout << s.top() << " ";
				s.pop();
			}
		}
	}
	while(s.empty()!=0)
	{
		sum=sum+s.top();
		s.pop();
	}
	cout << sum << endl;
	return 0;
}
